`
https://leetcode.cn/problems/is-graph-bipartite/
`

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
  const n = graph.length
  // 记录是否符合二分图性质
  let ok = true
  // 记录颜色，true 和 false 表示两种不同的颜色
  const color = new Array(n).fill(false)
  // 记录节点是否已经被访问过
  const visited = new Array(n).fill(false)

  const traverse = (v) => {
    // 如果不符合二分图性质，就没必要遍历了
    if (!ok) return

    visited[v] = true
    for (const w of graph[v]) {
      if (!visited[w]) {
        // 相邻节点 w 没有被访问过
        // 那么应该给节点 w 涂上和节点 v 不同的颜色
        color[w] = !color[v]
        traverse(w)
      } else {
        // 相邻节点 w 已经被访问过
        // 根据 v 和 w 的颜色判断是否是二分图
        if (color[v] === color[w]) {
          // 若相同，则此图不是二分图
          ok = false
        }
      }
    }
  }

  // 因为图不一定是联通的，可能存在多个子图
  // 所以要把每个节点都作为起点进行一次遍历
  // 如果发现任何一个子图不是二分图，整幅图都不算二分图
  for (let v = 0; v < n; v++) {
    if (!visited[v]) {
      traverse(v)
    }
  }

  return ok
};